import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 优选算法 day4: 滑动窗口
 * User: 姚东名
 * Date: 2024-12-13
 * Time: 21:21
 */
public class Test {
    /**
     * 14. 找到字符串中所有字⺟异位词（medium）
     * 首先通过遍历字符串p，使用HashMap（pMap）统计p中每个字符出现的频次，这作为后续判断异位词的一个参照标准。
     * <p>
     * 然后在遍历字符串s时，利用滑动窗口的思想，维护一个同样是HashMap类型的windowMap来记录窗口内字符的频次情况。
     * <p>
     * 随着窗口的移动（每遍历一个新字符，窗口向后滑动一位），不断更新windowMap。
     * 当窗口大小达到p的长度后，就需要把窗口最左边要移出的字符频次减 1，
     * 如果频次减到了 0，就从windowMap中移除该字符（因为它此时在窗口内已经不存在了）。
     * <p>
     * 最后，每次更新完windowMap后，都判断其与pMap是否相等，如果相等就意味着找到了一个异位词，
     * 此时把该异位词在s中的起始索引（通过i - pLen + 1计算得到，i是当前遍历到的索引，pLen是p的长度）添加到结果列表result中。
     * <p>
     * 在main1方法中，通过两个示例演示了该方法的调用，分别输出对应的异位词起始索引列表。
     *
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams1(String s, String p) {
        // 申请一个哈希表，记录p字符串中各字符的个数
        Map<Character, Integer> pMap = new HashMap<>();
        for (char c : p.toCharArray()) {
            pMap.put(c, pMap.getOrDefault(c, 0) + 1);
        }

        int pLen = p.length();
        // 记录滑动窗口的长度
        Map<Character, Integer> sMap = new HashMap<>();
        // 写一个集合来装起始索引
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            sMap.put(curChar, sMap.getOrDefault(curChar, 0) + 1);

            // 当窗口超过pLen时，开始收缩
            if (i >= pLen) {
                char leftChar = s.charAt(i - pLen);
                // 将最左边的字符的频率自减1
                sMap.put(leftChar, sMap.getOrDefault(leftChar, 0) - 1);
                if (sMap.get(leftChar) == 0) {
                    sMap.remove(leftChar);
                }
            }
            // 如果s中窗口的字符的频率和p相同，则记录起始索引
            if (sMap.equals(pMap)) {
                result.add(i - pLen + 1);
            }
        }
        return result;
    }

    public static void main1(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p));

        s = "abab";
        String newP = "ab";
        System.out.println(findAnagrams(s, newP));
    }

    // 代码优化
    public static List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数
        for (char ch : p) {
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数
        int m = p.length;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            // 进窗⼝ + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a']) {
                count++;
            }
            // 判断
            if (right - left + 1 > m) {
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                    count--;
                }
            }
            // 更新结果
            if (count == m) {
                ret.add(left);
            }
        }
        return ret;
    }

    /**
     * 15. 整串联所有单词的⼦串（hard）
     * 使用滑动窗口结合哈希表的方法来解决该问题。首先统计给定的words数组中每个单词出现的频次，
     * 然后通过在字符串s上滑动长度固定（等于所有words中单词长度之和）的窗口，判断窗口内的子串
     * 是否刚好是由words中的单词以某种顺序串联而成的，如果是则记录该窗口起始位置的索引到结果列表中。
     * 代码细节
     * <p>
     * 基础准备：
     * 首先在findSubstring方法中，定义了结果列表result，并进行了一些必要的合法性判断，比如输入的字符串s或者words数组为空等情况，直接返回空的结果列表。
     * 获取words中单个单词的长度wordLen，并根据单词个数和单个单词长度算出串联子串的总长度totalLen，后续通过这个长度来确定滑动窗口的大小。
     * 使用HashMap（wordsCountMap）来统计words数组中每个单词出现的频次，方便后续对比窗口内单词出现的情况。
     * <p>
     * 滑动窗口遍历：
     * 外层循环通过i来控制滑动窗口的起始位置，其范围是从0到s.length() - totalLen，保证窗口大小始终是totalLen这么长。
     * <p>
     * 在内层循环中，每次取出窗口内对应位置长度为wordLen的子串（通过substring方法获取），然后进行判断：
     * <p>
     * 如果取出的子串不在wordsCountMap中（即不在words数组里出现的单词集合里），
     * 直接跳出内层循环，因为这个窗口内不可能构成符合要求的串联子串了。
     * <p>
     * 如果子串在wordsCountMap中，就把该子串加入到另一个HashMap（seenCountMap）中记录其出现的次数，
     * 同时判断当前子串在窗口内出现的次数是否超过了在words中原本应有的次数，如果超过了同样跳出内层循环。
     * <p>
     * 当内层循环正常结束（也就是j的值等于words.length，
     * 意味着窗口内的子串刚好符合是由words中的单词串联而成的条件），
     * 就把当前窗口的起始索引i添加到结果列表result中。
     * <p>
     * 主函数测试：
     * 在main方法中，通过三个不同的示例来调用findSubstring方法并输出结果，直观展示代码对不同输入情况的处理效果。
     * 这段代码通过上述逻辑实现了在给定字符串s中查找所有能串联words数组中所有单词的子串起始索引的功能。
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：
     * 外层循环最多遍历s.length() - totalLen + 1次，内层循环最多遍历words.length次，
     * 每次操作哈希表的时间复杂度通常可以看作是常数级别（平均情况下），而获取子串的时间复杂度是和子串长度相关，
     * 这里子串长度固定为wordLen，所以整体时间复杂度大致为 ，其中n是字符串s的长度，m是words数组中单词的个数。
     * <p>
     * 空间复杂度：
     * 代码中使用了两个HashMap来分别记录words中单词出现的频次以及滑动窗口内单词出现的频次，
     * 哈希表中最多存放words数组里不同单词个数的键值对，所以空间复杂度大致为 ，
     * 这里k是words数组中不同单词的个数。
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || words == null || words.length == 0) {
            return result;
        }
        int wordLen = words[0].length();
        // 根据单词个数和单个单词长度算出串联子串的总长度
        int totalLen = wordLen * words.length;
        // 记录子串中各字符串的个数
        Map<String, Integer> wordsCountMap = new HashMap<>();
        for (String word : words) {
            wordsCountMap.put(word, wordsCountMap.getOrDefault(word, 0) + 1);
        }
        // 一共有words.length()中可能
        for (int i = 0; i <= s.length() - totalLen; i++) {
            Map<String, Integer> seenCountMap = new HashMap<>();
            int j;
            for (j = 0; j < words.length; j++) {
                int index = i + wordLen * j;
                String sub = s.substring(index, index + wordLen);
                // 如果当前子串不在words中出现的单词集合里，直接跳出循环
                if (!wordsCountMap.containsKey(sub)) {
                    break;
                }
                // 添加
                seenCountMap.put(sub, seenCountMap.getOrDefault(sub, 0) + 1);
                // 如果当前字串存在次数大于words，直接跳出循环
                if (seenCountMap.get(sub) > wordsCountMap.get(sub)) {
                    break;
                }
            }

            // 如果内层循环正常结束，说明找到了符合要求的串联子串
            if (j == words.length) {
                result.add(i);
            }
        }
        return result;
    }

    public static void main2(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo", "bar"};
        System.out.println(findSubstring(s, words));

        s = "wordgoodgoodgoodbestword";
        String[] newWords = {"word", "good", "best", "word"};
        System.out.println(findSubstring(s, newWords));

        s = "barfoofoobarthefoobarman";
        String[] anotherWords = {"bar", "foo", "the"};
        System.out.println(findSubstring(s, anotherWords));
    }

    //优化版本（最优解）
    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        // 保存字典中所有单词的频次
        Map<String, Integer> hash1 = new HashMap<>();
        for (String str : words) {
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }

        int len = words[0].length(), m = words.length;
        // 执行次数
        for (int i = 0; i < len; i++) {
            // 保存窗⼝内所有单词的频次
            Map<String, Integer> hash2 = new HashMap<>();
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                // 进窗⼝ + 维护 count
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                // 判断
                if (right - left + 1 > len * m) {
                    // 出窗⼝ + 维护 count
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                // 更新结果
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }

    // 方法错误：使用数组代替哈希表（在特定场景下更优）
    public static List<Integer> findSubstring3(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || words == null || words.length == 0) {
            return result;
        }
        int wordLen = words[0].length();
        int totalLen = wordLen * words.length;
        // 假设单词都由小写英文字母组成，用长度为26的数组统计words中单词频次
        int[] wordCountArr = new int[26];
        for (String word : words) {
            for (char c : word.toCharArray()) {
                wordCountArr[c - 'a']++;
            }
        }
        int[] seenArr = new int[26];
        for (int start = 0; start < wordLen; start++) {
            int i = start;
            while (i <= s.length() - totalLen) {
                Arrays.fill(seenArr, 0);
                int j;
                for (j = 0; j < words.length; j++) {
                    int index = i + j * wordLen;
                    String sub = s.substring(index, index + wordLen);
                    for (char c : sub.toCharArray()) {
                        seenArr[c - 'a']++;
                    }
                    boolean isValid = true;
                    for (int k = 0; k < 26; k++) {
                        if (seenArr[k] > wordCountArr[k]) {
                            isValid = false;
                            break;
                        }
                    }
                    if (!isValid) {
                        break;
                    }
                }
                if (j == words.length) {
                    result.add(i);
                }
                i += wordLen;
            }
        }
        return result;
    }

    // 16. 最小覆盖子串（hard）
    public static String minWindow2(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // 用于统计字符串t中各字符出现的频次
        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        // 用于统计滑动窗口内各字符出现的频次
        Map<Character, Integer> windowMap = new HashMap<>();
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        String result = "";
        int matchCount = 0;
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
            // 避免空指针异常，先判断窗口中字符是否在目标map中存在对应记录，再进行频次比较
            if (targetMap.containsKey(rightChar) && windowMap.get(rightChar).equals(targetMap.get(rightChar))) {
                matchCount++;
            }

            // 当窗口内已匹配的字符数等于t中字符种类数时，尝试收缩窗口
            while (matchCount == targetMap.size() && left <= right) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    result = s.substring(left, right + 1);
                }
                char leftChar = s.charAt(left);
                windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                // 同样避免空指针异常，先判断窗口中字符是否在目标map中存在对应记录，再进行频次相关判断
                if (targetMap.containsKey(leftChar) && windowMap.get(leftChar) < targetMap.get(leftChar)) {
                    matchCount--;
                }
                left++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String s1 = "ADOBECODEBANC";
        String t1 = "ABC";
        System.out.println(minWindow(s1, t1));

        String s2 = "a";
        String t2 = "a";
        System.out.println(minWindow(s2, t2));

        String s3 = "a";
        String t3 = "aa";
        System.out.println(minWindow(s3, t3));
    }

    // 代码优化：
    public static String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        // 统计字符串 t 中每⼀个字符的频次
        int[] hash1 = new int[128];
        // 统计有效字符有多少种
        int kinds = 0;
        for (char ch : t) {
            if (hash1[ch]++ == 0) {
                kinds++;
            }
        }
        // 统计窗⼝内每个字符的频次
        int[] hash2 = new int[128];

        int minlen = Integer.MAX_VALUE, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            // 进窗⼝ + 维护 count
            if (++hash2[in] == hash1[in]) {
                count++;
            }
            // 判断条件
            while (count == kinds) {
                // 更新结果
                if (right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if (hash2[out]-- == hash1[out]) {
                    count--;
                }
            }
        }
        if (begin == -1) {
            return new String();
        } else {
            return ss.substring(begin, begin + minlen);
        }
    }
}
